<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Linked List Intersection Visualizer</title>
    <script src="https://cdn.tailwindcss.com"></script>
    <style>
        .node {
            width: 60px;
            height: 60px;
            border-radius: 50%;
            display: flex;
            justify-content: center;
            align-items: center;
            position: relative;
            transition: all 0.3s ease;
        }
        
        .node-a {
            background-color: #93c5fd;
            color: #1e3a8a;
        }
        
        .node-b {
            background-color: #fca5a5;
            color: #7f1d1d;
        }
        
        .node-intersect {
            background-color: #86efac;
            color: #166534;
        }
        
        .pointer {
            width: 30px;
            height: 30px;
            border-radius: 50%;
            display: flex;
            justify-content: center;
            align-items: center;
            position: absolute;
            top: -15px;
            left: 15px;
            font-size: 12px;
        }
        
        .pointer-a {
            background-color: #3b82f6;
            color: white;
        }
        
        .pointer-b {
            background-color: #ef4444;
            color: white;
        }
        
        .arrow {
            position: absolute;
            width: 40px;
            height: 2px;
            background-color: #6b7280;
            top: 50%;
            right: -40px;
        }
        
        .arrow::after {
            content: '';
            position: absolute;
            width: 0;
            height: 0;
            border-top: 5px solid transparent;
            border-bottom: 5px solid transparent;
            border-left: 8px solid #6b7280;
            right: 0;
            top: -4px;
        }
        
        .highlight {
            box-shadow: 0 0 0 4px rgba(234, 179, 8, 0.5);
            transform: scale(1.1);
        }
        
        .list-container {
            display: flex;
            flex-direction: column;
            gap: 40px;
            margin-top: 20px;
        }
        
        .list-row {
            display: flex;
            gap: 10px;
            position: relative;
        }
        
        .controls {
            display: flex;
            gap: 10px;
            margin-top: 20px;
            justify-content: center;
        }
        
        .speed-control {
            display: flex;
            align-items: center;
            gap: 5px;
        }
        
        @keyframes fadeIn {
            from { opacity: 0; }
            to { opacity: 1; }
        }
        
        .explanation {
            animation: fadeIn 0.5s ease;
            background-color: #f3f4f6;
            padding: 15px;
            border-radius: 8px;
            margin-top: 20px;
        }
    </style>
</head>
<body class="bg-gray-50 min-h-screen p-8">
    <div class="max-w-4xl mx-auto">
        <h1 class="text-3xl font-bold text-center text-gray-800 mb-6">Linked List Intersection Visualizer</h1>
        
        <div class="bg-white rounded-lg shadow-md p-6">
            <div class="flex justify-between items-center mb-4">
                <h2 class="text-xl font-semibold text-gray-700">Visualization</h2>
                <div class="flex gap-2">
                    <span class="px-3 py-1 bg-blue-100 text-blue-800 rounded-full text-sm">List A</span>
                    <span class="px-3 py-1 bg-red-100 text-red-800 rounded-full text-sm">List B</span>
                    <span class="px-3 py-1 bg-green-100 text-green-800 rounded-full text-sm">Intersection</span>
                </div>
            </div>
            
            <div class="list-container">
                <div class="list-row" id="listA">
                    <!-- List A nodes will be inserted here -->
                </div>
                <div class="list-row" id="listB">
                    <!-- List B nodes will be inserted here -->
                </div>
            </div>
            
            <div class="controls">
                <button id="startBtn" class="px-4 py-2 bg-blue-600 text-white rounded hover:bg-blue-700 transition">Start</button>
                <button id="pauseBtn" class="px-4 py-2 bg-yellow-500 text-white rounded hover:bg-yellow-600 transition" disabled>Pause</button>
                <button id="resetBtn" class="px-4 py-2 bg-gray-600 text-white rounded hover:bg-gray-700 transition">Reset</button>
                <div class="speed-control">
                    <span class="text-sm text-gray-600">Speed:</span>
                    <input type="range" id="speedControl" min="100" max="2000" value="800" step="100" class="w-24">
                    <span id="speedValue" class="text-sm text-gray-600">0.8x</span>
                </div>
            </div>
            
            <div id="explanation" class="explanation hidden">
                <h3 class="font-medium text-gray-800 mb-2">Current Step Explanation</h3>
                <p id="explanationText" class="text-gray-600"></p>
            </div>
        </div>
        
        <div class="mt-8 bg-white rounded-lg shadow-md p-6">
            <h2 class="text-xl font-semibold text-gray-700 mb-4">Algorithm Explanation</h2>
            <p class="text-gray-600 mb-4">
                This visualization demonstrates how to find the intersection node of two linked lists using the two-pointer technique.
            </p>
            <ul class="list-disc pl-5 space-y-2 text-gray-600">
                <li>Initialize two pointers, one for each list (pa and pb)</li>
                <li>Traverse through the lists one node at a time</li>
                <li>When a pointer reaches the end of a list, redirect it to the head of the other list</li>
                <li>The pointers will eventually meet at the intersection node after traversing the same total distance</li>
                <li>If there's no intersection, both pointers will reach the end (null) at the same time</li>
            </ul>
        </div>
    </div>

    <script>
        document.addEventListener('DOMContentLoaded', function() {
            // Create the linked lists
            const c1 = { val: 8, next: null };
            const c2 = { val: 4, next: null };
            const c3 = { val: 5, next: null };
            c1.next = c2;
            c2.next = c3;
            
            // List A: 4 -> 1 -> 8 -> 4 -> 5
            const a1 = { val: 4, next: null };
            const a2 = { val: 1, next: null };
            a1.next = a2;
            a2.next = c1;
            
            // List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
            const b1 = { val: 5, next: null };
            const b2 = { val: 6, next: null };
            const b3 = { val: 1, next: null };
            b1.next = b2;
            b2.next = b3;
            b3.next = c1;
            
            // DOM elements
            const listAElement = document.getElementById('listA');
            const listBElement = document.getElementById('listB');
            const startBtn = document.getElementById('startBtn');
            const pauseBtn = document.getElementById('pauseBtn');
            const resetBtn = document.getElementById('resetBtn');
            const speedControl = document.getElementById('speedControl');
            const speedValue = document.getElementById('speedValue');
            const explanation = document.getElementById('explanation');
            const explanationText = document.getElementById('explanationText');
            
            // Animation state
            let animationId = null;
            let isPaused = false;
            let isRunning = false;
            let currentStep = 0;
            let speed = 800;
            
            // Render the initial lists
            function renderLists(pa = null, pb = null) {
                listAElement.innerHTML = '';
                listBElement.innerHTML = '';
                
                // Render List A
                let currentA = a1;
                while (currentA) {
                    const isIntersection = currentA === c1 || currentA === c2 || currentA === c3;
                    const isPa = currentA === pa;
                    
                    const node = document.createElement('div');
                    node.className = `node ${isIntersection ? 'node-intersect' : 'node-a'}`;
                    node.textContent = currentA.val;
                    
                    if (isPa) {
                        const pointer = document.createElement('div');
                        pointer.className = 'pointer pointer-a';
                        pointer.textContent = 'PA';
                        node.appendChild(pointer);
                        node.classList.add('highlight');
                    }
                    
                    listAElement.appendChild(node);
                    
                    if (currentA.next) {
                        const arrow = document.createElement('div');
                        arrow.className = 'arrow';
                        listAElement.appendChild(arrow);
                    }
                    
                    currentA = currentA.next;
                }
                
                // Render List B
                let currentB = b1;
                while (currentB) {
                    const isIntersection = currentB === c1 || currentB === c2 || currentB === c3;
                    const isPb = currentB === pb;
                    
                    const node = document.createElement('div');
                    node.className = `node ${isIntersection ? 'node-intersect' : 'node-b'}`;
                    node.textContent = currentB.val;
                    
                    if (isPb) {
                        const pointer = document.createElement('div');
                        pointer.className = 'pointer pointer-b';
                        pointer.textContent = 'PB';
                        node.appendChild(pointer);
                        node.classList.add('highlight');
                    }
                    
                    listBElement.appendChild(node);
                    
                    if (currentB.next) {
                        const arrow = document.createElement('div');
                        arrow.className = 'arrow';
                        listBElement.appendChild(arrow);
                    }
                    
                    currentB = currentB.next;
                }
            }
            
            // Initialize the visualization
            function init() {
                currentStep = 0;
                renderLists();
                explanation.classList.add('hidden');
            }
            
            // Run the algorithm step by step
            function runAlgorithm() {
                if (isPaused) return;
                
                let pa = a1;
                let pb = b1;
                let steps = [];
                
                // Pre-calculate all steps
                while (true) {
                    steps.push({
                        pa: pa,
                        pb: pb,
                        explanation: getExplanation(pa, pb)
                    });
                    
                    if (pa === pb) break;
                    
                    pa = pa ? pa.next : b1;
                    pb = pb ? pb.next : a1;
                    
                    // Safety check to prevent infinite loops
                    if (steps.length > 20) break;
                }
                
                // If we've completed all steps, stop
                if (currentStep >= steps.length) {
                    stopAnimation();
                    return;
                }
                
                // Show current step
                const step = steps[currentStep];
                renderLists(step.pa, step.pb);
                
                // Update explanation
                explanationText.textContent = step.explanation;
                explanation.classList.remove('hidden');
                
                currentStep++;
                
                // Continue animation
                animationId = setTimeout(runAlgorithm, speed);
            }
            
            // Get explanation for current step
            function getExplanation(pa, pb) {
                if (!pa && !pb) {
                    return "Both pointers have reached the end (null) at the same time. There is no intersection between the lists.";
                }
                
                if (pa === pb) {
                    if (pa === null) {
                        return "Both pointers have reached the end (null) at the same time. There is no intersection between the lists.";
                    } else {
                        return `Pointers PA and PB have met at node with value ${pa.val}. This is the intersection node!`;
                    }
                }
                
                let explanation = "";
                
                if (pa === null) {
                    explanation += "Pointer PA has reached the end of List A. ";
                    explanation += "It will now start traversing List B from the beginning. ";
                } else {
                    explanation += `Pointer PA is at node ${pa.val} in ${pa === a1 || pa === a2 ? 'List A' : 'the common part'}. `;
                }
                
                if (pb === null) {
                    explanation += "Pointer PB has reached the end of List B. ";
                    explanation += "It will now start traversing List A from the beginning.";
                } else {
                    explanation += `Pointer PB is at node ${pb.val} in ${pb === b1 || pb === b2 || pb === b3 ? 'List B' : 'the common part'}.`;
                }
                
                return explanation;
            }
            
            // Start animation
            function startAnimation() {
                if (isRunning) return;
                
                isRunning = true;
                isPaused = false;
                startBtn.disabled = true;
                pauseBtn.disabled = false;
                resetBtn.disabled = true;
                
                runAlgorithm();
            }
            
            // Pause animation
            function pauseAnimation() {
                if (!isRunning) return;
                
                isPaused = true;
                pauseBtn.disabled = true;
                startBtn.disabled = false;
                clearTimeout(animationId);
            }
            
            // Stop animation
            function stopAnimation() {
                isRunning = false;
                isPaused = false;
                startBtn.disabled = false;
                pauseBtn.disabled = true;
                resetBtn.disabled = false;
                clearTimeout(animationId);
            }
            
            // Reset animation
            function resetAnimation() {
                stopAnimation();
                init();
            }
            
            // Event listeners
            startBtn.addEventListener('click', startAnimation);
            pauseBtn.addEventListener('click', pauseAnimation);
            resetBtn.addEventListener('click', resetAnimation);
            
            speedControl.addEventListener('input', function() {
                speed = 2100 - this.value; // Invert so higher values = faster
                speedValue.textContent = `${(2100 - this.value) / 1000}x`;
                
                if (isRunning && !isPaused) {
                    clearTimeout(animationId);
                    animationId = setTimeout(runAlgorithm, speed);
                }
            });
            
            // Initialize
            init();
        });
    </script>
</body>
</html>